package leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class code543 {

    public  static  class  TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int size = scanner.nextInt();

        Integer[] arr = new Integer[size];

        for (int i = 0; i < size; i++) {
            arr[i] = scanner.nextInt();
        }

        //层次遍历构建二叉树
        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;

        while (queue.size() > 0){
            TreeNode currentNode = queue.poll();
            if (currentNode == null){
                continue;
            }
            else {
                if (i < arr.length && arr[i] != null){
                    currentNode.left = new TreeNode(arr[i]);
                    queue.offer(currentNode.left);
                }
                i++;
                if (i < arr.length && arr[i] != null){
                    currentNode.right = new TreeNode(arr[i]);
                    queue.offer(currentNode.right);
                }
                i++;
            }
        }

        System.out.println(diameterOfBinaryTree(root));

    }

    private static int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 计算左子树和右子树的最大深度
        int leftDepth = maxDepth(root.left);

        int rightDepth = maxDepth(root.right);

        // 计算左子树和右子树的最大直径
        int leftDiameter = diameterOfBinaryTree(root.left);

        int rightDiameter = diameterOfBinaryTree(root.right);

        return Math.max(leftDepth + rightDepth, Math.max(leftDiameter, rightDiameter));
    }

    private static int maxDepth(TreeNode left) {
        if (left == null) {
            return 0;
        }

        return Math.max(maxDepth(left.left), maxDepth(left.right)) + 1;
    }


}
